package com.cdream.basic.algorithm.leetcode.slideWindow;

import java.util.HashMap;
import java.util.Map;

/**
 * @author cdream
 * @date 6/2/21
 */
public class Question523 {
    public static void main(String[] args) {
        System.out.println(new Question523().checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6));
    }

    public boolean checkSubarraySum(int[] nums, int k) {
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
            // if (sum[i] % k == 0) {
            //     return true;
            // }
        }
        // for (int i = 0; i < sum.length; i++) {
        //     int index = i + 2;
        //     while (index <= sum.length - 1) {
        //         if ((sum[index] - sum[i]) % k == 0) {
        //             return true;
        //         }
        //         index++;
        //     }
        // }

        Map<Long, Integer> modMap = new HashMap<>();
        modMap.put(0L, -1);
        for (int i = 0; i < sum.length; i++) {
            long mod = sum[i] % k;
            Integer index = modMap.get(mod);
            if (index != null && i - index > 1) {
                return true;
            } else if (index == null) {
                modMap.put(mod, i);
            }
        }

        return false;

    }
}
